package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;
import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author By ZengPeng
 */
public class 力扣_993_二叉树的堂兄弟节点 {
    @Test
    public void main() {
        
        Solution solution = new 力扣_993_二叉树的堂兄弟节点().new Solution();
//        System.out.println(solution.isCousins(TreeNode.init(),5,4));
    }

    /**
     题目：在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
         如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
         我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
         只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

         示例 1：
         输入：root = [1,2,3,4], x = 4, y = 3
         输出：false

         示例 2：
         输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
         输出：true

         示例 3：
         输入：root = [1,2,3,null,4], x = 2, y = 3
         输出：false

     分析：【P 💖💖💖】
        1.遍历树：分别找到两个节点的路径，对比长度
                --执行耗时:0 ms,击败了100.00% 的Java用户
                --编码耗时:[27:06]

     边界值 & 注意点：
        1.
     **/
//leetcode submit region begin(Prohibit modification and deletion)
public  class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

 /*   public static TreeNode init(){
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode2 = new TreeNode(2,null,treeNode4);
        TreeNode treeNode3 = new TreeNode(3,null,treeNode5);
        TreeNode treeNode1 = new TreeNode(1,treeNode2,treeNode3);
        return treeNode1;
    }*/
}
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        Deque<TreeNode> dequeX = new ArrayDeque<>();
        dfs(root,x,dequeX);
        Deque<TreeNode> dequeY = new ArrayDeque<>();
        dfs(root,y,dequeY);
        return dequeY.size()==dequeX.size() && dequeX.peek()!=dequeY.peek();
    }

    private boolean dfs(TreeNode root, int i, Deque<TreeNode> deque) {
        if(root==null)
            return false;
        if(root.val==i)
            return true;
        if(dfs(root.left,i,deque) || dfs(root.right,i,deque)){
            deque.add(root);
            return true;
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}